除了i-node，hash是另一種用來儲存磁碟資料的方法。
除了i-node，hash是另一種用來儲存磁碟資料的方法。Hash簡單的說就是透過特殊的函數**(hash function)產生對應資料的key值，而這個值要盡可能地避免重複，以減少查詢時的失誤(兩個以上的資料對應到相同的key，一般稱為碰撞**)。另外，同一個資料在同一個hash function的作用之下，永遠都會產生相同的key。反過來，輸入key值，就可以得到確切的資料。在檔案系統中，這些key值代表的是index，而這些key值就表格的形式(hash table)儲存起來。

Hash 的一大優點是，透過hash function查表只是固定時間的動作(演算法術語: constant time)，但是卻點就是key的碰撞在所難免。這是一個設計上的衝突，越複雜的hash function設計可以盡可能地避免key值得碰撞，但是卻增加了設計的難度，以及影響執行的效率。比較折衷的方法有：1. 將有相同的key值的資料串再一起，2. 遇到碰撞時再次進行其他的hash function運算。第一種折衷方式是最常見的，將擁有相同key值的資料串在一起，然後再依序查詢。理論上只要hash function不要太差，這個串列就不會太長，影響也就有限了。

Hash 本身還有兩個(小)缺點，剛剛說到key值以hash tabale的形式儲存下來，這表格當然是有所限制的。而如果表格小一點，占用的空間可以少一點，但是相對的資料碰撞的機會就增加；反之，表格大一點，減少了資料碰撞，但是也造成空間的浪費。有一中動態hash table的設計，但是每當table變更時，key值就需要重新計算，這樣反而影響效能。還有，key值本身沒有順序，所以無法在hash table中進行尋訪的動作(in-order traversal)，這動作是為了加速查詢的結果。

系列文章